package code.linkedlist;

import java.util.Scanner;

/**
 * @ClassName LRUBaseLinkedList
 * @Description 基于单链表LRU算法（java）
 * @Author za-zhouyunxing
 * @Date 2019/8/27 14:57
 * @Version 1.0
 */
public class LRUBaseLinkedList<T> {

    /**
     * 默认链表容量
     */
    private final static Integer DEFAULT_CAPACITY = 10;

    /**
     * 头结点
     */
    private SNode<T> headNode;


    /**
     * 链表长度
     */
    private Integer length;

    /**
     * 链表容量
     */
    private Integer capacity;

    public LRUBaseLinkedList() {
        this.headNode = new SNode<>();
        this.length = 0;
        this.capacity = DEFAULT_CAPACITY;
    }

    public LRUBaseLinkedList(Integer  capacity) {
        this.headNode = new SNode<>();
        this.length = 0;
        this.capacity = capacity;
    }

    /**
     * 添加元素
     * @param data
     */
    public void add(T data){
        SNode preNode = findPreNode(data);
        if (preNode != null){
            // 链表中存在，删除原数据，再插入到链表的头部
            deleteElemOptim(preNode);
            intsertElemAtBegin(data);
        }else {
            //链表中不存在
            if (length >= capacity){
                //删除尾节点
                deleteElemAtEnd();
            }
            intsertElemAtBegin(data);
        }
    }

    /**
     * 打印所有节点
     */
    private void printAll() {
        SNode node = headNode.getNext();
        while (node != null) {
            System.out.print(node.getElement() + ",");
            node = node.getNext();
        }
        System.out.println();
    }

    /**
     * 删除尾结点
     */
    private void deleteElemAtEnd() {
        SNode preNode = headNode;
        //空链表直接返回
        if (preNode.next == null){
            return;
        }
        //获取倒数第二个节点
        while (preNode.getNext().getNext() != null){
            preNode = preNode.getNext();
        }
        //删除尾节点
        SNode temp = preNode.getNext();
        preNode.setNext(null);
        temp = null;
        length --;
    }

    /**
     * 链表头部插入节点
     *
     * @param data
     */
    private void intsertElemAtBegin(T data) {
        SNode next = headNode.getNext();
        headNode.setNext(new SNode(data, next));
        length ++;
    }

    /**
     * 删除preNode结点下一个元素
     *
     * @param preNode
     */
    private void deleteElemOptim(SNode preNode){
        SNode temp = preNode.getNext();
        preNode.setNext(temp.getNext());
        temp = null;
        length--;
    }

    /**
     * 获取查找到元素的前一个结点
     *
     * @param data
     * @return
     */
    private  SNode findPreNode(T data){
        SNode node = headNode;
        while (node.getNext() != null){
            if (data.equals(node.getNext().getElement())){
                return node;
            }
            node = node.getNext();
        }
        return null;
    }



    public class SNode<T>{

        private T element;

        private SNode next;

        public SNode(T element) {
            this.element = element;
        }

        public SNode(T element, SNode next) {
            this.element = element;
            this.next = next;
        }

        public SNode() {
            this.next = null;
        }

        public T getElement() {
            return element;
        }

        public void setElement(T element) {
            this.element = element;
        }

        public SNode getNext() {
            return next;
        }

        public void setNext(SNode next) {
            this.next = next;
        }
    }

    public static void main(String[] args) {
        LRUBaseLinkedList list = new LRUBaseLinkedList();
        Scanner scanner = new Scanner(System.in);
        while (true){
            list.add(scanner.nextInt());
            list.printAll();
        }
    }

}
